package tree.searchTree;

import leetcode.leetcode144.TreeNode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @author czt
 * @version 1.0
 * @since 2024/12/30
 */
public class BSTree1 {

    static class BSTNode {

        int key;

        Object value;

        BSTNode left;

        BSTNode right;

        public BSTNode(int key) {
            this.key = key;
        }

        public BSTNode(int key, Object value) {
            this.key = key;
            this.value = value;
        }

        public BSTNode(int key, Object value, BSTNode left, BSTNode right) {
            this.key = key;
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }

    BSTNode root; // 根节点

    /**
     * 查找关键字对应的值
     * @param key 关键字
     * @return 值
     */
    public Object get(int key) {
        //return doGet(root, key); // 递归方法
        BSTNode node = root;
        while (node != null) {
            if (key < node.key) {
                node = node.left;
            } else if (key > node.key) {
                node = node.right;
            } else {
                return node.value;
            }
        }
        return null;
    }

    private Object doGet(BSTNode node, int key) {
        if (node == null) return null;
        // 待查找的key小于当前节点的key，找左边
        if (key < node.key) {
            return doGet(node.left, key);
        // 待查找的key小于当前节点的key，找左边
        } else if (key > node.key) {
            return doGet(node.right, key);
        } else {
        // 找到返回
            return node.value;
        }
    }

    /**
     * 查找最小关键字的值
     * @return 值
     */
    public Object min() {
        BSTNode node = root;
        if (root == null) return null;
        while (node.left != null) {
            node = node.left;
        }
        return node.value;
    }

    private Object getMin(BSTNode node) {
        if (node == null) return null;
        while (node.left != null) {
            node = node.left;
        }
        return node.value;
    }

    /**
     * 查找最大关键字的值
     * @return 值
     */
    public Object max() {
        BSTNode node = root;
        if (root == null) return null;
        while (node.right != null) {
            node = node.right;
        }
        return node.value;
    }

    private Object getMax(BSTNode node) {
        if (node == null) return null;
        while (node.right != null) {
            node = node.right;
        }

        return node.value;
    }

    /**
     * 存储关键字和对应的值
     * @param key 关键字
     * @param value 值
     */
    public void put(int key, Object value) {

        BSTNode node = root;
        BSTNode parent = null; // 用来记录待添加节点的父节点
        while (node != null) {
            parent = node;
            if (key < node.key) {
                node = node.left;
            } else if (key > node.key) {
                node = node.right;
            } else {
                // 1.key存在，更新
                node.value = value;
                return;
            }
        }
        // 如果父节点为空，说明没有节点，那么新增的节点为根节点
        if (parent == null) {
            root = new BSTNode(key,value);
            return;
        }
        // 2.key不存在，添加
        if (key < parent.key) {
            parent.left = new BSTNode(key, value);
        } else {
            parent.right = new BSTNode(key, value);
        }
    }

    /**
     * 查找关键字的前驱值
     * @param key 关键字
     * @return 前驱值
     *
     * 1.节点有左子树，此时前驱节点就是左子树的最大值
     * 2.节点没有左子树，若离他最近的祖先从左而来，此祖先为前驱
     */
    public Object successor(int key) {
        BSTNode p = root;
        // 自左而来的祖先，在寻找节点时，一直在记录节点的祖先节点，
        // 如果经历 p = p.left，说明这个祖先自右而来；如果经历 p = p.right，说明这个祖先自右而来
        BSTNode zxFromLeft = null; // 记录子左而来的祖先
        while (p != null) {
            if (key < p.key) {
                p = p.left;
            } else if (key > p.key) {
                zxFromLeft = p;
                p = p.right;
            } else {
                break;
            }
        }

        if (p == null) return null;

        /*
        1.节点有左子树，此时前驱节点就是左子树的最大值
        2.节点没有左子树，若离他最近的祖先从左而来，此祖先为前驱
         */

        if (p.left != null) {
            // 1.节点有左子树，此时前驱节点就是左子树的最大值
            return getMax(p.left);
        }

        // 2.节点没有左子树，若离他最近的祖先从左而来，此祖先为前驱
        return zxFromLeft != null ? zxFromLeft.value : null;
    }

    /**
     * 查找关键字的后继值
     * @param key 关键字
     * @return 后继值
     *
     * 1.节点有右子树，此时后继节点即为右子树的最小值
     * 2.节点没有右子树，若它最近的祖先从右而来，此祖先为后继
     */
    public Object predecessor(int key) {
        BSTNode p = root;
        // 自左而来的祖先，在寻找节点时，一直在记录节点的祖先节点，
        // 如果经历 p = p.left，说明这个祖先自右而来；如果经历 p = p.right，说明这个祖先自右而来
        BSTNode zxFromRight = null; // 记录子左而来的祖先
        while (p != null) {
            if (key < p.key) {
                zxFromRight = p;
                p = p.left;
            } else if (key > p.key) {
                p = p.right;
            } else {
                break;
            }
        }

        if (p == null) return null;

        /*
        1.节点有右子树，此时后继节点即为右子树的最小值
        2.节点没有右子树，若它最近的祖先从右而来，此祖先为后继
         */

        if (p.right != null) {
            // 1.节点有右子树，此时后继节点即为右子树的最小值
            return getMin(p.right);
        }

        // 2.节点没有右子树，若它最近的祖先从右而来，此祖先为后继
        return zxFromRight != null ? zxFromRight.value : null;
    }

    private List<Object> inorderTraversal(BSTNode node) {
        List<Object> list = new ArrayList<>();
        Stack<BSTNode> stack = new Stack<>();
        while (node != null || !stack.isEmpty()) {
            if (node != null) {
                stack.push(node);
                node = node.left;
            } else {
                BSTNode pop = stack.pop();
                list.add(pop.key);
                node = pop.right;
            }
        }
        return list;
    }

    /**
     * 根据关键字删除
     * @param key 关键字
     * @return 被删除关键字的对应值-value
     *
     *
     */
    public Object delete(int key) {
        BSTNode node = root; // 当前节点
        BSTNode parent = null; // 父节点
        // 查找节点
        while (node != null) {
            if (key < node.key) {
                parent = node;
                node = node.left;
            } else if (key > node.key) {
                parent = node;
                node = node.right;
            } else {
                break;
            }
        }
        // 没找到
        if (node == null) return null;

        if (node.left == null) {
            // 1.删除节点没有左孩子，将右孩子托孤给parent，左右孩子都没有也可以处理
            shift(parent,node,node.right);
        } else if (node.right == null) {
            // 2.删除节点没有右孩子，将左孩子托孤给parent
            shift(parent, node, node.left);
        } else {
            // 3.1 被删除节点找后继
            BSTNode s = node.right;
            BSTNode sParent = node;
            while (s.left != null) {
                sParent = s;
                s = s.left;
            }
            // 3.2 处理后继的后事(后继节点和删除节点不相邻)
            if (sParent != node) {
                // 不相邻
                shift(sParent,s,s.right); // 不可能有左孩子，因为s是被删除节点的后继节点
                s.right = node.right;
            }
            // 3.3 后继取代被删除的节点
            shift(parent,node,s);
            s.left = node.left;
        }
        return node.value;
    }

    /**
     * 托孤方法
     * @param parent 被删除节点的父节点
     * @param deleted 被删除节点
     * @param child 被顶上去的节点
     */
    private void shift(BSTNode parent, BSTNode deleted, BSTNode child) {
        // 被删除节点没有父节点，说明为根节点，此时他的子节点变为根节点
        if (parent == null) {
            root = child;
        } else if (deleted == parent.left) {
            parent.left = child;
        } else {
            parent.right = child;
        }

    }

    // 中序遍历思想，解决下面的范围查询问题

    // 找小于 key 的所有值
    public List<Object> less(int key) {
        ArrayList<Object> result = new ArrayList<>();
        BSTNode node = root;

        Stack<BSTNode> stack = new Stack<>();
        while (node != null || !stack.isEmpty()) {
            if (node != null) {
                stack.push(node);
                node = node.left;
            } else {
                BSTNode pop = stack.pop();
                // 如果小于，则加入
                if (pop.key < key) {
                    result.add(pop.value);
                } else {
                    break;
                }
                node = pop.right;
            }
        }
        return result;
    }

    // 找大于 key 的所有值
    public List<Object> greater(int key) {
        ArrayList<Object> result = new ArrayList<>();
        BSTNode node = root;

        Stack<BSTNode> stack = new Stack<>();
        while (node != null || !stack.isEmpty()) {
            if (node != null) {
                stack.push(node);
                node = node.left;
            } else {
                BSTNode pop = stack.pop();
                if (pop.key > key) {
                    result.add(pop.key);
                } else {
                    break;
                }
                node = pop.right;
            }
        }
        return result;
    }

    // 找 key1<=x<=key2的值
    public List<Object> between(int key1, int key2) {
        ArrayList<Object> result = new ArrayList<>();
        BSTNode node = root;

        Stack<BSTNode> stack = new Stack<>();
        while (node != null || !stack.isEmpty()) {
            if (node != null) {
                stack.push(node);
                node = node.left;
            } else {
                BSTNode pop = stack.pop();
                if (pop.key >= key1 && pop.key <= key2) {
                    result.add(pop.key);
                } else if (pop.key > key2) {
                    break;
                }
                node = pop.right;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        System.out.println(27*15);
    }


}
